package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/19 14:41
 *
 *
 剪绳子:
 1,动态规划
 状态定义：设dp(i)为长度为i时，分出的绳子乘积的“最大值”
 状态划分与状态转移：
 任何一段绳子可以分为2段，一段长一段短，然后长的那段(设短的长度为j)就是子问题dp(i-j)
 转移方程——dp(i)=max(j*dp(i-j)) j=[1,i/2]

 2,数学，贪心：均值不等式，暂时不掌握
 */

public class Main46 {


    public int cutRope(int target) {
        //特判，前几个不满足转移方程
        if(target<=3)return target-1;
        //初始化，并让前几个满足方程
        int dp[]=new int[target+1];
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        for(int i=4;i<=target;++i){
            //遍历，集合划分
            for(int j=1;j<=i/2;++j){
                dp[i]=Math.max(dp[i],j*dp[i-j]);
            }
        }
        return dp[target];
    }
}
